A processor cache, whether used for instructions or data or both, is inherently of a finite capacity or size. When a cache is “full,” e.g., all possible cache memory locations are utilized, a determination must be made of which information to discard, or “evict,” in order to add new information to the cache. The mechanism or “rule” for making such a determination is known as or referred to as a “replacement policy.”
An ideal replacement policy would be to always evict the information that will not be used (again) for the longest time period. As a practical matter, it is impossible to know when information will be needed in the future. Hence, many replacement policies make predictions based on the age, or time since last use, of cached information.
One such replacement policy is known as or referred to as “Least Recently Used (LRU).” An LRU replacement policy discards or evicts the least recently used cache items first. An LRU replacement policy generally requires keeping track of what was used when, which may be considered expensive in terms of storage and processing time if a system wants to make sure the algorithm always discards the uniquely least recently used item.
An alternative replacement policy is known as or referred to as “Pseudo Least Recently Used (PLRU).” A PLRU replacement policy generally discards or evicts one of, or approximately the oldest cached items, although the discarded item may not be the uniquely least recently used item. A PLRU replacement policy generally trades a lack of evicting exactly the least recently used cached item in favor of reduced storage and processing time.
Unfortunately, conventional PLRU replacement policies are generally insufficient for a computer system requiring multiple cache look up requests in the same clock cycle.